package com.sicheng.lc.周赛.分类.栈.单调栈or单调队列;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/10 21:33
 */
@SuppressWarnings("all")
public class 子数组的最小值之和 {
    //https://leetcode.cn/problems/sum-of-subarray-minimums/
    static int N = (int) (3 * 1e4);
    static int[] left = new int[N];
    static int[] right = new int[N];
    static int mod = (int) (1e9 + 7);

    {
        Arrays.fill(left, 0);
        Arrays.fill(right, N);
    }

    public int sumSubarrayMins(int[] nums) {
        int n = nums.length;
        ArrayDeque<Integer> stack = new ArrayDeque<>(n);
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                left[i] = stack.peek() + 1;
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                right[i] = stack.peek() - 1;
            }
            stack.push(i);
        }
        long res = 0;
        for (int i = 0; i < nums.length; i++) {
            int L = left[i], R = Math.min(n - 1, right[i]);
            res = (res + (long) (i - L + 1) * (R - i + 1) * nums[i] % mod) % mod;
        }
        return (int) res;
    }
}
